//
// Created by ZYZ on 2020/6/17.
//

#include <stdio.h>
#include <stdlib.h>
#include "../../include/define.h"
#include "../../include/type_linked_queue.h"
#include "linked_queue.h"

//队列是有一个空的头结点，队头指针 Q.front 指向该头结点的地址，队尾指针 Q.rear 指向最后一个元素的地址

Status InitQueue(LinkQueue &Q) {
    //构造一个空队列 Q
    Q.front = Q.rear = (QueuePtr) malloc(sizeof(QNode));
    if (!Q.front) exit(OVERFLOW); //存储分配失败
    Q.front->next = NULL;
    return OK;
}

//判空
Status QueueEmpty(LinkQueue Q) {
    if (Q.front == Q.rear) {
        return OK;
    } else {
        return ERROR;
    }
}//QueueEmpty

//返回Q的元素的个数
int QueueLength(LinkQueue Q) {
    int len = 0;
    QueuePtr p = Q.front;
    // 队头到队尾遍历计算长度
    while (p != Q.rear) {
        p = p->next;
        len++;
    }
    return len;
}//QueueLength_Sq

//获取队头元素
Status GetHead(LinkQueue Q, QElemType &e) {
    if (Q.front == Q.rear) {
        return ERROR;
    }
    QNode *p = Q.front->next;
    e = p->data;
    return OK;
}

//清空队列
Status ClearQueue(LinkQueue & q) {
    // 获取队头元素
    QueuePtr p = q.front->next;
    QueuePtr temp;
    // 遍历释放各节点
    while (p) {
        temp = p;
        free(temp);
        p = p->next;
    }
    // 重置队头与队尾
    q.front->next = NULL;
    q.rear = q.front;
    return OK;
}

//销毁队列 Q
Status DestroyQueue(LinkQueue &Q) {
    while (Q.front) {
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
    return OK;
}

//插人元素 e 为 Q 的新的队尾元素
Status EnQueue(LinkQueue &Q, QElemType e) {

    auto p = (QueuePtr) malloc(sizeof(QNode));
    if (!p) exit(OVERFLOW); //存储分配失败

    p->data = e;
    p->next = NULL;
    Q.rear->next = p;       //添加到队尾，即链表后面
    Q.rear = p;             //将队尾指针移动到队尾位置

    return OK;
}

//若队列不空，则删除 Q 的队头元素，用 e 返回其值，并返回 0K; 否则返回 ERROR
Status DeQueue(LinkQueue &Q, QElemType &e) {

    if (Q.front == Q.rear) return ERROR;

    QueuePtr p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;

    if (Q.rear == p)         //因为是每次都从队头删除元素，如果 Q.rear == p，则删除的是最后一个元素，此时重置队尾
        Q.rear = Q.front;
    free(p);

    return OK;
}

//遍历
Status QueueTraverse(LinkQueue Q, Status  (*visit)(QElemType e)) {
    if (QueueEmpty(Q)) {
        return ERROR;
    }
    QueuePtr p = Q.front->next;
    while (p) {
//        printf("%d ", p->data);
        visit(p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}